
/**
 * Author: 刘俊重
 * Resource：https://leetcode-cn.com/problems/maximum-subarray/
 * Resolution: https://blog.csdn.net/linhuanmars/article/details/21314059
 */
public class Main {
    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(maxSubArray(nums));
    }

    public static int maxSubArray(int[] nums){
        if(nums == null || nums.length<0){
            return 0;
        }
        //局部最优解
        int local = nums[0];
        //全局最优解
        int global = nums[0];
        for(int i=1;i<nums.length;i++){
            local = Math.max(nums[i],nums[i]+local);
            global = Math.max(local,global);
        }
        return global;
    }
}
